// Heap sort.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <iostream>
using namespace std;

int Parent(int i) {
	return ( (i-1) % 2 == 0) ? (i-1)/2 : (i-2)/2;
}

int left(int i) {
	return (2*i+1);
}

int Right(int i) {
	return (2*i+2);
}

void Max_HeapIFY( vector<int>& A, int i, int heap_size ) {
	//int heap_size = A.size();
	int l, r;
	int largest;
	int temp;
	l = left(i);
	r = Right(i);
	if ( l < heap_size && A[l] > A[i] )
		largest = l;
	else
		largest = i;
	if ( r < heap_size && A[r] > A[largest] )
		largest = r;
	if ( largest != i ) {
		temp = A[i];
		A[i] = A[largest];
		A[largest] = temp;
		Max_HeapIFY(A, largest, heap_size);
	}
	return;
}

void Build_Max_Heap( vector<int>& A, int heap_size ) {
	int i;
	for ( i = (A.size()-1) / 2; i >=0; --i)
		Max_HeapIFY(A, i, heap_size);
	for ( vector<int> :: iterator ivecb = A.begin(); ivecb != A.end(); ++ ivecb )
		cout << *ivecb << "\t";
	cout << endl;
}

void Heap_sort( vector<int>& A ) {
	int heap_size = A.size();
	int i;
	int temp;
	Build_Max_Heap(A, heap_size);
	for ( i = (A.size()-1); i >= 1; --i) {
		temp = A[0];
		A[0] = A[i];
		A[i] = temp;
		heap_size = heap_size - 1;
		Max_HeapIFY(A, 0, heap_size);
	}
}

int main()
{
	vector<int> H;
	int buffer;
	cout << "please input an array of numbers." << endl;
	while (cin >> buffer)
		H.push_back(buffer);
	Heap_sort(H);
	for ( vector<int>::iterator ivec = H.begin(); ivec != H.end(); ++ivec)
		cout << *ivec << '\t';
	cout << endl;
	return 0;
}

